package com.shm.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 384. 打乱数组
 * 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
 *
 * 实现 Solution class:
 *
 * Solution(int[] nums) 使用整数数组 nums 初始化对象
 * int[] reset() 重设数组到它的初始状态并返回
 * int[] shuffle() 返回数组随机打乱后的结果
 *
 *
 * 示例：
 *
 * 输入
 * ["Solution", "shuffle", "reset", "shuffle"]
 * [[[1, 2, 3]], [], [], []]
 * 输出
 * [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
 *
 * 解释
 * Solution solution = new Solution([1, 2, 3]);
 * solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
 * solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
 * solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 200
 * -106 <= nums[i] <= 106
 * nums 中的所有元素都是 唯一的
 * 最多可以调用 5 * 104 次 reset 和 shuffle
 *
 *
 * 方法一：暴力
 *  * 思路
 *  *
 *  * 首先，我们考虑如何随机打乱一个数组。
 *  *
 *  * 不妨设数组 \textit{nums}nums，其长度为 nn。我们可以使用如下方法打乱：
 *  *
 *  * 将数组中所有的数都放到数据结构 \textit{waiting}waiting 中，并初始化打乱后的数组 \textit{shuffle}shuffle；
 *  * 循环 nn 次，在第 ii 次循环中（0 \le i < n0≤i<n）：
 *  * 在 \textit{waiting}waiting 中随机抽取一个数 \textit{num}num，将其作为打乱后的数组 \textit{shuffle}shuffle 的第 ii 个元素；
 *  * 从 \textit{waiting}waiting 中移除 \textit{num}num。
 *  * 对于原数组 \textit{nums}nums 中的数 \textit{num}num 来说，被移动到打乱后的数组的第 ii 个位置的概率为：
 *  *
 *  * P(i) = \begin{cases} (\frac{n-1}{n} \times \frac{n-2}{n-1} \cdots \times \frac{n-i}{n-i+1}) \times \frac{1}{n-i} = \frac{1}{n}, \hspace{1em} i > 0 \\ \frac{1}{n}, \hspace{1em} i = 0 \end{cases}
 *  * P(i)={
 *  * (
 *  * n
 *  * n−1
 *  * ​
 *  *  ×
 *  * n−1
 *  * n−2
 *  * ​
 *  *  ⋯×
 *  * n−i+1
 *  * n−i
 *  * ​
 *  *  )×
 *  * n−i
 *  * 1
 *  * ​
 *  *  =
 *  * n
 *  * 1
 *  * ​
 *  *  ,i>0
 *  * n
 *  * 1
 *  * ​
 *  *  ,i=0
 *  * ​
 *  *
 *  *
 *  * 因此，对于原数组 \textit{nums}nums 中的任意一个数，被移动到打乱后的数组的任意一个位置的概率都是相同的。
 *  *
 *  * 算法
 *  *
 *  * 在算法的实现中，我们考虑以下两个问题：
 *  *
 *  * 如何实现重设数组到它的初始状态？
 *  *
 *  * 我们使用 \textit{nums}nums 来存储当前数组，并用 \textit{original}original 来存储数组的初始状态。在需要重设数组到它的初始状态时，只需要将 \textit{original}original 复制到 \textit{nums}nums 并返回即可。
 *  *
 *  * 如何实现 \textit{waiting}waiting？
 *  *
 *  * 我们要求 \textit{waiting}waiting 既支持根据随机计算的下标获取元素，又支持根据该下标移除元素。在方法一中，我们使用数组来实现 \textit{waiting}waiting。
 *  *
 *  * 作者：LeetCode-Solution
 *  * 链接：https://leetcode-cn.com/problems/shuffle-an-array/solution/da-luan-shu-zu-by-leetcode-solution-og5u/
 *  * 复杂度分析
 *
 * 时间复杂度：
 * 初始化：O(n)O(n)，其中 nn 为数组中的元素数量。我们需要 O(n)O(n) 来初始化 \textit{original}original。
 * \texttt{reset}reset：O(n)O(n)。我们需要 O(n)O(n) 将 \textit{original}original 复制到 \textit{nums}nums。
 * \texttt{shuffle}shuffle：O(n^2)O(n
 * 2
 *  )。我们需要遍历 nn 个元素，每个元素需要 O(n-k)O(n−k) 的时间从 \textit{nums}nums 中移除第 kk 个元素。
 * 空间复杂度：O(n)O(n)。记录初始状态和临时的乱序数组均需要存储 nn 个元素。
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode-cn.com/problems/shuffle-an-array/solution/da-luan-shu-zu-by-leetcode-solution-og5u/
 */
class ShuffleArraySolution {
    int[] origin;
    public ShuffleArraySolution(int[] nums) {
        this.origin = nums;
    }
    
    public int[] reset() {
        return origin;
    }
    
    public int[] shuffle() {
        int[] shuffle = new int[origin.length];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < origin.length; i++) {
            list.add(origin[i]);
        }
        Random random = new Random();
        for (int i = 0; i < origin.length; i++) {
            int j = random.nextInt(list.size());
            shuffle[i] = list.remove(j);
        }
        return shuffle;
    }
}